from collections import deque
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs=[#坐标
    lambda x,y:(x+1,y),#下
    lambda x,y:(x-1,y),#上
    lambda x,y:(x,y-1),#左
    lambda x,y:(x,y+1)#右
]
def print_r(path):
    curNode=path[-1]

    realpath=[]
    while curNode[2]!=-1:
        #realpath.append(curNode[0],curNode[1])
        realpath.append(curNode[0:2])
        curNode=path[curNode[2]]
    realpath.append(curNode[0:2])#-1跳出来了，-1为起点，把起点放进去

    #realpath为路径(倒着的)
    realpath.reverse()
    for node in realpath:
        print(node)
def math_path_queue(x1,y1,x2,y2):
    queue=deque()
    queue.append((x1,y1,-1))
    path=[]
    while len(queue)>0:
        curNode=queue.popleft()# 当前节点是队首节点，并将队首节点出队
        path.append(curNode)#记录出队节点
        if curNode[0] == x2 and curNode[1]==y2:
            #终点
            print_r(path)
            return True
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]]==0:
                queue.append((nextNode[0],nextNode[1],len(path)-1))#后续节点进队，记录哪个节点带他来的
                maze[nextNode[0]][nextNode[1]]=2#标记已经走过
    else:
        print("没有路")
        return False
if __name__=="__main__":
    math_path_queue(1,1,8,8)